package test02;

import java.util.List;

public class LinkedList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode pre;
        ListNode(int x) {
            val = x;
        }
    }
    public ListNode head;

    public ListNode createList (){
        addFirst(11);
        addFirst(22);
        addFirst(33);
        addFirst(44);
        addFirst(55);
        return head;
    }

    //头插法
    public void addFirst(int data){
        ListNode Node = new ListNode(data);
        if(head == null){
            head = Node;
        }
        else{
            Node.next = head;
            head.pre = Node;
            head = Node;
        }
    }
    //尾插法
    public void addLast(int data){
        if(head == null){
            addFirst(data);
        }
        else{
            ListNode Node = new ListNode(data);
            ListNode cur = head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = Node;
            Node.pre = cur;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        int len = size();
        if(head == null){
            addFirst(data);
        }
        else{
            if(index < 0 || index > len){
                return false;
            }
            ListNode cur = head;
            for(int i = 0; i < index; i++){
                cur = cur.next;
            }
            ListNode Node = new ListNode(data);
            Node.next = cur;
            Node.pre = cur.pre;
            cur.pre.next = Node;
            cur.pre = Node;
        }
        return true;

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head == null){
            return false;
        }
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(contains(key)){
            ListNode cur = head;
            while(cur!= null){
                if(cur.val == key){
                    if(cur.pre == null){
                        head = cur.next;
                    }else if(cur.next == null){
                        cur.pre.next = null;
                    }else{
                        cur.pre.next = cur.next;
                        cur.next.pre = cur.pre;
                    }
                    return;
                }
                cur = cur.next;
            }
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(contains(key)){
            ListNode cur = head;
            while(cur!= null){
                if(cur.val == key){
                    if(cur.pre == null){
                        head = cur.next;
                    }else if(cur.next == null){
                        cur.pre.next = null;
                    }else{
                        cur.pre.next = cur.next;
                        cur.next.pre = cur.pre;
                    }
                }
                cur = cur.next;
            }
        }
    }
    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
    public void display(){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
    public void clear(){
        head = null;

    }


        public ListNode partition(ListNode pHead, int x) {

            ListNode cur = pHead;
            for(int i = 0; i < size(); i++) {
                if (cur.val > x) {
                    ListNode temp = cur;
                    addLast(temp.val);
                    remove(temp.val);
                }
                cur = cur.next;
            }
            return cur;
        }

}